#pragma once
#include<vector>
enum State
{
	EMPTY,
	EXIST,
	DELETE
};
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K, class V, class es>
class HashTable
{
public:
	HashTable()
		:_tables(11)
		,_n(0)
	{
	}
	bool insert(const pair<K,V>& kv)
	{
		es as;
		if (find(kv.first))
		{
			return false;
		}
		if (_n *10/ _tables.size() >= 7)
		{
			HashTable<K, V,es> newtable;
			newtable._tables.resize(_tables.size() * 2);
			for (auto& e : _tables)
			{
				if(e._state==EXIST)
				newtable.insert(e._kv);
			}
			_tables.swap(newtable._tables);
		}
		size_t hash0 = as(kv.first)% _tables.size();
		size_t i = 1;
		size_t hashi = hash0;
		while (_tables[hashi]._state==EXIST)
		{
			hashi=(hash0+i)% _tables.size();
			i++;
		}
		_n++;
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		return true;
	}
	HashData<K, V>* find(const K& key)
	{
		es as;
		size_t hash0 = as(key) % _tables.size();
		size_t i = 1;
		size_t hashi = hash0;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state==EXIST&&as(_tables[hashi]._kv.first) == as(key))
			{
				return &_tables[hashi];
			}
			hashi = (hash0 + i) % _tables.size();
			i++;
		}
		return nullptr;
	}
	bool erase(const K& key)
	{
		HashData<K, V>*  ret=find(key);
		if (ret)
		{
			ret->_state = DELETE;
		}
		else
		{
			return false;
		}
	}
private:
	vector<HashData<K, V>> _tables;
	size_t _n=0;
};